package avlTree;

public class AvlTree {
    static class TreeNode{
        public int val;
        public int bf;//平衡因子
        public TreeNode left=null;//左子树的引用
        public TreeNode right=null;//右子树的引用
        public TreeNode parent=null;//父亲节点的引用
        public TreeNode(int val){
            this.val=val;
        }
    }
    public TreeNode root;
    public boolean insert(int val){//AVL树节点的插入
        TreeNode node=new TreeNode(val);
        if(root==null){
            root=node;
            return true;
        }
        TreeNode cur=root;
        TreeNode p=null;
        while (cur!=null){
            if(cur.val<val){
                p=cur;
                cur=cur.right;
            }
            else if(cur.val>val){
                p=cur;
                cur=cur.left;
            }
            else{
                return false;
            }
        }
        if(val> p.val){
            p.right=node;
        }
        else {
            p.left=node;
        }
        node.parent=p;
        cur=node;
        //调节平衡因子
        while(p!=null){
            if(cur==p.right){
                p.bf++;
            }
            else{
                p.bf--;
            }
            if(p.bf==0){
                break;
            }
            else if(Math.abs(p.bf)==1){
                cur=p;
                p=p.parent;
            }
            else{
                if(p.bf==2){
                    if(cur.bf==1){
                        //左旋
                        rotateL(p);
                    }
                    else{
                        //先右旋后左旋
                        rotateRL(p);
                    }
                }
                else {
                    if(cur.bf==1){
                        //先左旋后右旋
                        rotateLR(p);
                    }
                    else{
                        //右旋
                        rotateR(p);
                    }
                }
            }
        }
        return true;
    }

    private void rotateLR(TreeNode parent) {
        TreeNode SubL=parent.left;
        TreeNode SubLR=SubL.right;
        int bf=SubLR.bf;
        rotateL(parent.left);
        rotateR(parent);
        if(bf==1){
            SubL.bf=-1;
            SubLR.bf=0;
            parent.bf=0;
        }
        else if(bf==-1){
            parent.bf=1;
            SubL.bf=0;
            SubLR.bf=0;
        }
        else {
            SubL.bf= SubLR.bf=parent.bf=0;
        }
    }

    private void rotateRL(TreeNode parent) {
        TreeNode SubR=parent.right;
        TreeNode SubRL=SubR.left;
        int bf=SubRL.bf;
        rotateR(parent.right);
        rotateL(parent);
        if(bf==1){
            parent.bf=-1;
            SubR.bf=0;
            SubRL.bf=0;
        }
        else if(bf==-1){
            SubR.bf=0;
            parent.bf=0;
            SubRL.bf=1;
        }
        else {
            SubR.bf=SubRL.bf= parent.bf=0;
        }
    }

    private void rotateL(TreeNode parent) {
        TreeNode SubR=parent.right;
        TreeNode SubRL=SubR.left;
        SubR.left=parent;
        parent.right=SubRL;
        TreeNode pParent=parent.parent;
        parent.parent=SubR;
        if(SubRL!=null){
            SubRL.parent=parent;
        }
        if(parent==root){
            root=SubR;
            SubR.parent=null;
        }
        else{
            if(pParent.left==parent){
                pParent.left=SubR;
            }
            else if(pParent.right==parent){
                pParent.right=SubR;
            }
            SubR.parent=pParent;
        }
        //更新平衡因子
        SubR.bf=0;
        parent.bf=0;
    }

    private void rotateR(TreeNode parent) {
        TreeNode SubL=parent.left;
        TreeNode SubLR=SubL.right;
        SubL.right=parent;
        parent.left=SubLR;
        TreeNode pParent=parent.parent;
        parent.parent=SubL;
        if(SubLR!=null){
            SubLR.parent=parent;
        }
        if(parent==root){
            root=SubL;
            SubL.parent=null;
        }
        else{
            if(pParent.left==parent){
                pParent.left=SubL;
            }
            else if(pParent.right==parent){
                pParent.right=SubL;
            }
            SubL.parent=pParent;
        }
        //更新平衡因子
        SubL.bf=0;
        parent.bf=0;
    }
    private int TreeHigh(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftH=TreeHigh(root.left);
        int rightH=TreeHigh(root.right);
        return leftH>rightH?leftH+1:rightH+1;
    }
    public void inorder(TreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left);
        System.out.println(root.val+" ");
        inorder(root.right);
    }
    public boolean isBalance(TreeNode root){
        if(root==null){
            return true;
        }
        int leftH=TreeHigh(root.left);
        int rightH=TreeHigh(root.right);
        if (rightH-leftH!=root.bf){
            System.out.println("这个节点"+root.val+"平衡因子异常");
        }
        return Math.abs(leftH-rightH)<2&&isBalance(root.right)&&isBalance(root.left);
    }
}
